package com.suanfa.sort;

/**
 * Created by buguniao on 16/2/8.
 * 外层for循环定位到当前位置需要确定的数组上
 * 内层循环为了确定当前位置及其后面位置上元素的最小值下标
 * 将最小值交换到当前位置上
 * 将当前位置移动到下一个位置，将下一个位置设为当前位置
 *
 * 需要1/2*n^2次比较
 * 无论数组的初始状态什么样都需要这么长时间，与初始状态没有关系，与数组大小有关系
 */
public class Selection extends SuanFaTemplate{
    public static void main(String[] args){
        Selection selection = new Selection();
        double[] arr = selection.getRandomArray(64000);
        long time=selection.run(arr);
        System.out.print("time cost : "+time);
    }

    public long run(double[] arr){
        long t1 = System.currentTimeMillis();
        for(int i=0;i<arr.length;i++){
            int min=i;
            for(int j=i+1;j<arr.length;j++){
                if(less(arr[j],arr[min])){
                    min=j;
                }
            }
            exchange(arr,i,min);
        }
        long t2 = System.currentTimeMillis();
        return t2-t1;
    }
}
